package sort.quickSort;

import java.util.Stack;

/**
 * @Author: zhang
 * @Description:快排非递归
 * @Date: Created in 1:38 2019/9/20
 */
public class quickSortByStackTest {
    public static void main(String[] args) {
        int[] arrays = new int[]{5, 1, 7, 4, 8, 9, 2, 3, 6, 0};
        quickSortByStack(arrays);
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + " ");
        }
    }

    //非递归实现快排：使用栈
    public static void quickSortByStack(int[] a) {
        Stack<Integer> stack = new Stack<>();
        //初始状态的左右下标入栈
        stack.push(0);
        stack.push(a.length - 1);
        while (!stack.isEmpty()) {
            //出栈两个元素用来划分待排序数组
            // 注意：进栈的时候先低位下标，出栈的时候先出来的是高位
            int high = stack.pop();
            int low = stack.pop();
            //找基准
            int pivotIndex = partition(a, low, high);
            //保存划分后左半部分两个下标
            if (pivotIndex > low + 1) {
                stack.push(low);
                stack.push(pivotIndex - 1);
            }
            //保存划分后右半部分两个下标，增加pivotIndex >= 0，过滤partition返回的-1
            if (pivotIndex < high - 1 && pivotIndex >= 0) {
                stack.push(pivotIndex + 1);
                stack.push(high);
            }
        }
    }

    public static int partition(int[] a, int left, int right) {
        if (left >= right) {
            return -1;
        }
        //保存基准的值
        int pivot = a[left];
        while (left < right) {
            //从后向前找比基准小的元素，插入到基准位置
            while (left < right && a[right] >= pivot) {
                right--;
            }
            a[left] = a[right];
            //从前向后找比基准大的元素
            while (left < right && a[left] <= pivot) {
                left++;
            }
            a[right] = a[left];
        }
        //放置基准值
        a[left] = pivot;
        //返回基准下标
        return left;
    }
}
